{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Changes to Make Binary String Beautiful"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minChanges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使二进制字符串变美丽的最少修改次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为偶数下标从 <strong>0</strong>&nbsp;开始的二进制字符串&nbsp;<code>s</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果可以将一个字符串分割成一个或者更多满足以下条件的子字符串，那么我们称这个字符串是 <strong>美丽的</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个子字符串的长度都是 <strong>偶数</strong>&nbsp;。</li>\n",
    "\t<li>每个子字符串都 <strong>只</strong>&nbsp;包含 <code>1</code>&nbsp;或 <strong>只</strong>&nbsp;包含 <code>0</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以将 <code>s</code>&nbsp;中任一字符改成&nbsp;<code>0</code>&nbsp;或者&nbsp;<code>1</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回让字符串 <code>s</code>&nbsp;美丽的<strong>&nbsp;最少</strong>&nbsp;字符修改次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"1001\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>我们将 s[1] 改为 1 ，且将 s[3] 改为 0 ，得到字符串 \"1100\" 。\n",
    "字符串 \"1100\" 是美丽的，因为我们可以将它分割成 \"11|00\" 。\n",
    "将字符串变美丽最少需要 2 次修改。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"10\"\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>我们将 s[1] 改为 1 ，得到字符串 \"11\" 。\n",
    "字符串 \"11\" 是美丽的，因为它已经是美丽的。\n",
    "将字符串变美丽最少需要 1 次修改。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"0000\"\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>不需要进行任何修改，字符串 \"0000\" 已经是美丽字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;的长度为偶数。</li>\n",
    "\t<li><code>s[i]</code>&nbsp;要么是&nbsp;<code>'0'</code>&nbsp;，要么是&nbsp;<code>'1'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-changes-to-make-binary-string-beautiful](https://leetcode.cn/problems/minimum-number-of-changes-to-make-binary-string-beautiful/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-changes-to-make-binary-string-beautiful](https://leetcode.cn/problems/minimum-number-of-changes-to-make-binary-string-beautiful/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1001\"', '\"10\"', '\"0000\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)//2):\n",
    "            a = s[2*i]\n",
    "            b = s[2*i+1]\n",
    "            if a != b:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n=len(s)//2\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if s[2*i]!=s[2*i+1]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        num=len(s)\n",
    "        result=0\n",
    "        for item in range(0,num,2):\n",
    "            if s[item]!=s[item+1]:\n",
    "                result+=1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n // 2):\n",
    "            if s[i << 1] != s[(i << 1) + 1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n=len(s)//2\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if s[2*i]!=s[2*i+1]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < n-1:\n",
    "            if s[i] != s[i+1]:\n",
    "                ans += 1\n",
    "            i += 2\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        return sum(s[i] != s[i + 1] for i in range(0, len(s), 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        return sum(s[i] != s[i + 1] for i in range(0, len(s), 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(0,len(s),2):\n",
    "            if s[i]!=s[i+1]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(s),2):\n",
    "            if s[i]!=s[i-1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        return sum(s[i] != s[i + 1] for i in range(0, len(s), 2))\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n = int(len(s) / 2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if s[2 * i] != s[2 * i + 1]:\n",
    "                ans += 1\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        return sum(s[i] != s[i+1] for i in range(0, len(s), 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n = int(len(s) / 2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if s[2 * i] != s[2 * i + 1]:\n",
    "                ans += 1\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(0, len(s), 2):\n",
    "            if s[i + 1] != s[i]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        cur = \"\"\n",
    "        cnt = 0\n",
    "        for i in range(len(s)):\n",
    "            if cur==\"\":\n",
    "                cur = s[i]\n",
    "                cnt = 1\n",
    "            elif cur == s[i]:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                if cnt%2==0:\n",
    "                    cur = s[i]\n",
    "                    cnt = 1\n",
    "                else:\n",
    "                    cur = \"\"\n",
    "                    cnt = 0\n",
    "                    ans+=1\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans=0\n",
    "        for x in range(0,len(s),2):\n",
    "            if s[x] != s[x+1]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans=0\n",
    "        for x in range(0,len(s),2):\n",
    "            if s[x] != s[x+1]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(0, len(s), 2):\n",
    "            if s[i] != s[i + 1]:\n",
    "                res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(0,len(s),2):\n",
    "            if s[i] != s[i+1]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        return sum(s[i] != s[i + 1] for i in range(0, len(s), 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, a: str) -> int:\n",
    "        # print(*range(0, len(a) - 1, 2))\n",
    "        ans = sum(1 if a[i] != a[i + 1] else 0 for i in range(0, len(a) - 1, 2))\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(Solution.minChanges(None, \"101110\"))\n",
    "    print(Solution.minChanges(None, \"1001\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(0, len(s), 2):\n",
    "            if s[i] != s[i+1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        lon=len(s)\n",
    "        q=s[0]\n",
    "        cal=1\n",
    "        ans=0\n",
    "        for i in range(1,lon):\n",
    "            if s[i]==q:\n",
    "                cal+=1\n",
    "            else:\n",
    "                if cal%2==1:\n",
    "                    ans+=1\n",
    "                    cal=2\n",
    "                else:\n",
    "                    cal=1\n",
    "                q=s[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        temp = [0] * (n//2)\n",
    "        one = \"1\"\n",
    "        for i,c in enumerate(s):\n",
    "            if c == one:\n",
    "                temp[i//2] += 1\n",
    "        used = 0\n",
    "        for v in temp:\n",
    "            if not v%2:\n",
    "                continue\n",
    "            used += 1\n",
    "        return used"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "\n",
    "        # dp(i, v, x)表示前面排尾数值是v, 且奇偶性是x情况下 i位置和其后面部分做决策的最少变换次数\n",
    "\n",
    "        dp0 = [[0, 0], [0, 0]]\n",
    "        dp1 = [[0, 0], [0, 0]]\n",
    "\n",
    "        n = len(s)\n",
    "        if s[n-1] == '0':\n",
    "            dp0[0][0] = 0x7f7f7f7f\n",
    "            dp0[0][1] = 0\n",
    "            dp0[1][0] = 0x7f7f7f7f\n",
    "            dp0[1][1] = 1\n",
    "\n",
    "        else:\n",
    "            dp0[0][0] = 0x7f7f7f7f\n",
    "            dp0[0][1] = 0x7f7f7f7f\n",
    "            dp0[1][0] = 1\n",
    "            dp0[1][1] = 0\n",
    "\n",
    "        for i in range(n-2, 0, -1):\n",
    "            if s[i] == '0':\n",
    "                dp1[0][0] = min( dp0[0][1], 1 + dp0[1][1] )\n",
    "                dp1[0][1] = min( dp0[0][0], 0x7f7f7f7f )\n",
    "                dp1[1][0] = min( dp0[0][1], 1 + dp0[1][1] )\n",
    "                dp1[1][1] = min( 1 + dp0[1][0], 0x7f7f7f7f)\n",
    "            else:\n",
    "                dp1[0][0] = min( dp0[1][1], 1 + dp0[0][1] )\n",
    "                dp1[0][1] = min( 1 + dp0[0][0], 0x7f7f7f7f )\n",
    "                dp1[1][0] = min( dp0[1][1], 1 + dp0[0][1] )\n",
    "                dp1[1][1] = min ( dp0[1][0], 0x7f7f7f7f )\n",
    "\n",
    "            dp0, dp1 = dp1, dp0\n",
    "\n",
    "\n",
    "        if s[0] == '0':\n",
    "            ans = min( dp0[0][1], 1 + dp0[1][1] )\n",
    "        else:\n",
    "            ans = min( dp0[1][1], 1 + dp0[0][1] )\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        return sum([1 for i in range(n // 2) if s[2 * i] != s[2 * i + 1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        return sum([1 for i in range(0, len(s), 2) if s[i] != s[i + 1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        s = list(s)\n",
    "        for n, c in enumerate(s):\n",
    "            if n % 2 == 0:k = c\n",
    "            else:\n",
    "                if c != k:ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        nums = list(s)\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(0,n,2):\n",
    "            if nums[i+1] != nums[i]:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache, reduce\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')  # 负无穷\n",
    "INFMAX = float('inf')  # 正无穷\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "'''\n",
    "gcd(), ord(), chr(), lower(), upper() 最大公约数/ASCII字符数值/数值ASCII字符/小写/大写\n",
    "startswith(s), endswith(s), find(), index(), count(s)  字符串是否以s开始的/字符串是否以s结尾的/查找返回的是索引/获取索引\n",
    "isalpha(), isdigit(), space(),join()  判断是否全为字符/判断是否全为数字/判断是否为空格/拼接\n",
    "eval() 字符串转换成列表、元组或者字典/\n",
    "uniform(x, y), pow(x, y)# 随机生成下一个实数，它在[x,y]范围内/ x**y 运算后的值。\n",
    "字典推倒式 {key: len(key) for key in list}\n",
    "列表推倒式 [i for i in range(100) if i % 3 == 0] 可切片,可索引,可重复\n",
    "集合推倒式 {i ** 2 for i in (1, 2, 3)}  不可索引,不可切片,不可重复元素\n",
    "'''\n",
    "\n",
    "# 数值和字母进行转换 ord()函数是把字符转换成ASCII码 chr()函数是把ASCII码转换成字符\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "# lcm 最小公倍数 gcd 最大公约数\n",
    "def lcm(x, y):\n",
    "    return x * y // gcd(x, y)\n",
    "\n",
    "# 快速幂\n",
    "def qpow(x, y):\n",
    "    ans = 1\n",
    "    while y:\n",
    "        if y & 1:\n",
    "            ans *= x\n",
    "        x *= x\n",
    "        y >>= 1\n",
    "    return ans\n",
    "\n",
    "# 求组合数\n",
    "def Comb(n, m, p):\n",
    "    a = (factorial(n)) % p\n",
    "    b = (qpow(factorial(m), (p - 2), p)) % p\n",
    "    c = (qpow(factorial(n - m), (p - 2), p)) % p\n",
    "    return a * b * c % p\n",
    "\n",
    "# lucas求组合数\n",
    "def Lucas(n, m, p):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    return Comb(n % p, m % p, p) * Lucas(n // p, m // p, p) % p\n",
    "\n",
    "def rep():\n",
    "    a = list(map(int, input().split()))\n",
    "    return a\n",
    "\n",
    "def sep():\n",
    "    a = input().rstrip('\\n')\n",
    "    return a\n",
    "\n",
    "# --idea \n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/11/26 23:24\n",
    "\n",
    "\"\"\"\n",
    "考虑最后被分成几个满足条件的字符串，那么它们每一个必定是由多个11，\n",
    "或者由多个00组成，所以修改次数也就是看看相邻两项相同还是不相同，相同不操作，不相同则加1\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        return sum(s[i] != s[i + 1] for i in range(0, len(s), 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        i = 0\n",
    "        while i < n :\n",
    "            if s[i-1] != s[i] :\n",
    "                if count % 2 != 0 :\n",
    "                    s[i] = '1' if s[i] == '0' else '0'\n",
    "                    count = -1\n",
    "                    ans += 1\n",
    "                else :\n",
    "                    count = 0\n",
    "            count += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        for i in range(0, n-1, 2):\n",
    "            if s[i] == s[i+1]: continue\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 给你一个长度为偶数下标从 0 开始的二进制字符串 s 。\n",
    "\n",
    "# 如果可以将一个字符串分割成一个或者更多满足以下条件的子字符串，那么我们称这个字符串是 美丽的 ：\n",
    "\n",
    "# 每个子字符串的长度都是 偶数 。\n",
    "# 每个子字符串都 只 包含 1 或 只 包含 0 。\n",
    "# 你可以将 s 中任一字符改成 0 或者 1 。\n",
    "\n",
    "# 请你返回让字符串 s 美丽的 最少 字符修改次数。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        ans = 0\n",
    "        arr = list(s)\n",
    "        while right < n:\n",
    "            if arr[left] == arr[right]:\n",
    "                res += 1\n",
    "            else:\n",
    "                if res % 2 != 0:\n",
    "                    \n",
    "                    ans += 1\n",
    "                    arr[right] = \"1\" if arr[right] == \"0\" else \"0\"\n",
    "                    res = 0\n",
    "                        \n",
    "                else:\n",
    "                    \n",
    "                    \n",
    "                    res = 1\n",
    "                    left = right\n",
    "            right += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        l = list(s)\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(0, n, 2):\n",
    "            if s[i] != s[i + 1]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        s = list(s)\n",
    "        ans = 0\n",
    "        for i in range(1, len(s), 2):\n",
    "            if s[i] != s[i - 1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        return sum([int(s[i] != s[i + 1]) for i in range(0, n, 2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        s=list(s)\n",
    "        n=len(s)\n",
    "        cnt=0\n",
    "        i=0\n",
    "        j=0\n",
    "        while i<n:\n",
    "            while j<n and s[i]==s[j]:\n",
    "                j+=1\n",
    "            if j<n and (j-i)%2!=0:\n",
    "                cnt+=1\n",
    "                if j<n:\n",
    "                    if s[i]=='1':\n",
    "                        s[j]='0'\n",
    "                    else:\n",
    "                        s[j]='1'\n",
    "                    j+=1\n",
    "\n",
    "            i=j\n",
    "        return cnt\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        t = s[0]\n",
    "        c = 0\n",
    "        s = s+'8'\n",
    "        p = []\n",
    "        for i in range(n+1):\n",
    "            if s[i] == t:\n",
    "                c += 1\n",
    "            else:\n",
    "                p.append(c)\n",
    "                t = s[i]\n",
    "                c = 1\n",
    "        k = len(p)\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            if p[i]%2==1:\n",
    "                ans += 1\n",
    "                if i<k-1:\n",
    "                    p[i+1] += 1\n",
    "                else:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        s = [int(d) for d in s]\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and s[j] == s[i]:\n",
    "                j += 1\n",
    "            if (j - i) % 2 == 1:\n",
    "                ans += 1\n",
    "                s[j] = 1 - s[j]\n",
    "                j += 1\n",
    "            i = j\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        pre=None\n",
    "        arr=[]\n",
    "        for lt in s:\n",
    "            if pre and lt==pre:\n",
    "                arr[-1]+=1\n",
    "            else:\n",
    "                if lt=='0':\n",
    "                    pre='0'\n",
    "                else:\n",
    "                    pre='1'\n",
    "                arr.append(1)\n",
    "        # print(arr)\n",
    "        cnt=0\n",
    "        flag=False\n",
    "        # res=[]\n",
    "        for i in arr:\n",
    "            if not flag:\n",
    "                if i%2==1:\n",
    "                    flag=True\n",
    "                    tmp=1\n",
    "            elif flag:\n",
    "                if i%2==0:\n",
    "                    tmp+=1\n",
    "                else:\n",
    "                    cnt+=tmp\n",
    "                    tmp=0\n",
    "                    flag=False\n",
    "            # res.append(flag)\n",
    "        # print(res)\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        nums = [0]\n",
    "        pre = s[0]\n",
    "        for c in s:\n",
    "            if c == pre:\n",
    "                nums[-1] += 1\n",
    "            else:\n",
    "                nums.append(1)\n",
    "                pre = c\n",
    "        res = 0\n",
    "        f = 0\n",
    "        for num in nums:\n",
    "            if (num + f) % 2 == 0:\n",
    "                f = 0\n",
    "            else:\n",
    "                f = 1\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict, deque\n",
    "from heapq import heappop, heappush, heapify, heapreplace, heappushpop, nlargest, nsmallest\n",
    "from bisect import bisect_left, bisect_right\n",
    "from math import inf, gcd, lcm, log, log2, ceil, floor\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList, SortedDict\n",
    "from itertools import accumulate, combinations, permutations, pairwise\n",
    "from functools import lru_cache, reduce, cmp_to_key\n",
    "\n",
    "# sys.set_int_max_str_digits(20000)  # 设置最大字符串位数\n",
    "MOD = 10 ** 9 + 7\n",
    "DIR = ((-1, 0), (0, 1), (1, 0), (0, -1))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        for i in range(1, n, 2):\n",
    "            if s[i] != s[i - 1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        l=[]\n",
    "        b=0\n",
    "        for i,c in enumerate(s):\n",
    "            if i>0 and c!=s[i-1]:\n",
    "                l.append(i-b)\n",
    "                b=i\n",
    "        l.append(n-b)\n",
    "        rm=0\n",
    "        res=0\n",
    "        for a in l:\n",
    "            if (a+rm)%2==0:\n",
    "                rm=0\n",
    "            else:\n",
    "                res+=1\n",
    "                rm=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        sublen = []\n",
    "        if not s:\n",
    "            return 0\n",
    "        pre = s[0]\n",
    "        cnt = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == pre:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                sublen.append(cnt)\n",
    "                cnt = 1\n",
    "                pre = s[i]\n",
    "        sublen.append(cnt)\n",
    "        ans = 0\n",
    "        for i in range(len(sublen)):\n",
    "            if sublen[i] % 2:\n",
    "                sublen[i] -= 1\n",
    "                sublen[i+1] += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        c = s[0]\n",
    "        f = 1\n",
    "        counts = []\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == c:\n",
    "                f += 1\n",
    "            else:\n",
    "                counts.append(f)\n",
    "                c = s[i]\n",
    "                f = 1\n",
    "        counts.append(f)\n",
    "        num_ops = 0\n",
    "        for i in range(len(counts) - 1):\n",
    "            if counts[i] % 2 == 1:\n",
    "                num_ops += 1\n",
    "                counts[i] -= 1\n",
    "                counts[i + 1] += 1\n",
    "        return num_ops"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        ans=[]\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if s[i]=='1':\n",
    "                x=0\n",
    "                while i<n and s[i]=='1':\n",
    "                    i+=1\n",
    "                    x+=1\n",
    "                ans.append(x%2)\n",
    "            if i==n:\n",
    "                break\n",
    "            if s[i]=='0':\n",
    "                x=0\n",
    "                while i<n and s[i]=='0':\n",
    "                    i+=1\n",
    "                    x+=1\n",
    "                ans.append(x%2)\n",
    "        tot=0\n",
    "        p=len(ans)\n",
    "        i=0\n",
    "        while i<p:\n",
    "            if ans[i]==1:\n",
    "                tot+=1\n",
    "                ans[i+1]=1-ans[i+1]\n",
    "                i+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return tot\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0]*(n//2)\n",
    "        if(s[0] == s[1]):\n",
    "            dp[0] = 0\n",
    "        else:\n",
    "            dp[0] = 1\n",
    "        for i in range(1,n//2):\n",
    "            if(s[i*2]==s[i*2+1]):\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "        return dp[n//2-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        print(s)\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        i = 0\n",
    "        while i < n :\n",
    "            if s[i-1] != s[i] :\n",
    "                if count % 2 != 0 :\n",
    "                    s[i] = '1' if s[i] == '0' else '0'\n",
    "                    count = -1\n",
    "                    ans += 1\n",
    "                else :\n",
    "                    count = 0\n",
    "            count += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, s: str) -> int:\n",
    "        nums = []\n",
    "\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            cnt = 0\n",
    "            pre = s[i]\n",
    "            while i < n and s[i] == pre:\n",
    "                i += 1\n",
    "                cnt += 1\n",
    "            nums.append(cnt % 2)\n",
    "\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num:\n",
    "                ans += 1\n",
    "                if i + 1 < len(nums):\n",
    "                    nums[i + 1] ^= 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
